/*
 * @lc app=leetcode.cn id=37 lang=golang
 *
 * [37] 解数独
 */
package main

import "fmt"

// @lc code=start

func solveSudoku(board [][]byte) {
	var line, column [9][9]bool
	var block [3][3][9]bool // 3 * 3 的小正方形
	var spaces [][2]int

	for i, row := range board {
		for j, b := range row {
			if b == '.' {
				spaces = append(spaces, [2]int{i, j})
			} else {
				digit := b - '1'
				line[i][digit] = true
				column[j][digit] = true
				block[i/3][j/3][digit] = true
			}
		}
	}

	var dfs func(int) bool
	dfs = func(pos int) bool {
		if pos == len(spaces) {
			return true
		}
		i, j := spaces[pos][0], spaces[pos][1]
		for digit := byte(0); digit < 9; digit++ {
			if !line[i][digit] && !column[j][digit] && !block[i/3][j/3][digit] {
				line[i][digit] = true
				column[j][digit] = true
				block[i/3][j/3][digit] = true
				board[i][j] = digit + '1'
				if dfs(pos + 1) {
					return true
				}
				line[i][digit] = false
				column[j][digit] = false
				block[i/3][j/3][digit] = false
			}
		}
		return false
	}
	dfs(0)
}

// @lc code=end

func main() {
	/*
		board := [][]byte{[]byte("53..7...."),
			[]byte("6..195..."),
			[]byte(".98....6."),
			[]byte("8...6...3"),
			[]byte("4..8.3..1"),
			[]byte("7...2...6"),
			[]byte(".6....28."),
			[]byte("...419..5"),
			[]byte("....8..79")}
	*/
	board := [][]byte{[]byte("2........"),
		[]byte("........."),
		[]byte("........."),
		[]byte("........."),
		[]byte("........."),
		[]byte("........."),
		[]byte("........."),
		[]byte("........."),
		[]byte(".87654321")}
	solveSudoku(board)
	/*
		for i := range board {
			fmt.Printf("%s\n", string(board[i]))
			// fmt.Println(string(board[i]))
		}*/
	for i := range board {
		for j := range board[i] {
			fmt.Printf(" %c ", board[i][j])
		}
		fmt.Println()
	}
}
